/**
 * 
 */
package ro.dta.idbi.model.dynamicpattern;

import java.util.Arrays;

import ro.dta.idbi.interfaces.IGraphIsomorphism;

/**
 * Implementation of the VF2 (Vento-Foggia 2) algorithm to check if two graphs
 * are isomorphic
 * 
 * @author Tudor Dobrila
 * 
 */
public class VFIsomorphism implements IGraphIsomorphism {

	/**
	 * The adjacency matrix of the first graph
	 */
	private int[][] graph1;

	/**
	 * The adjacency matrix of the second graph
	 */
	private int[][] graph2;

	/**
	 * Mapping from the vertices of the first graph to the vertices of the
	 * second graph
	 */
	private int[] core1;

	/**
	 * Mapping from the vertices of the second graph to the vertices of the
	 * first graph
	 */
	private int[] core2;

	/**
	 * The in and out arrays for each of the two graphs, as defined in the
	 * original paper of the algorithm
	 */
	private int[] in1, out1, in2, out2;

	/**
	 * The number of vertices that each of the two graphs contains
	 */
	private int noVertices;

	/**
	 * Temporary counters for the in and out arrays, as defined in the original
	 * paper of the algorithm
	 */
	private int countIn1, countIn2, countOut1, countOut2;

	/**
	 * Total execution time of the last run
	 */
	private long totalTime;

	/**
	 * Vento-Foggia 2 algorithm class constructor
	 */
	public VFIsomorphism() {

	}

	@Override
	public int[] areIsomorphic(int[][] graph1, int[][] graph2) {
		if (graph1.length != graph1[0].length || graph1.length != graph2.length
				|| graph1[0].length != graph2[0].length) {
			// Graphs have different no. of vertices
			return null;
		}

		long startTime = System.currentTimeMillis();

		// Initialise the variables of the algorithm
		this.graph1 = graph1;
		this.graph2 = graph2;
		noVertices = graph1.length;
		core1 = new int[noVertices];
		Arrays.fill(core1, -1);
		core2 = new int[noVertices];
		Arrays.fill(core2, -1);
		in1 = new int[noVertices];
		out1 = new int[noVertices];
		in2 = new int[noVertices];
		out2 = new int[noVertices];
		countOut1 = 0;
		countOut2 = 0;
		countIn1 = 0;
		countIn2 = 0;

		// Start recursion
		boolean result = recursionStep(1);
		totalTime = System.currentTimeMillis() - startTime;
		if (result) {
			return core1;
		}

		return null;
	}

	private boolean recursionStep(int t) {
		if (t == noVertices + 1) {
			return true;
		}

		// In case that only one of the in-terminal sets or only one of the
		// out-terminal sets is empty, return false
		if ((countIn1 == 0 && countIn2 != 0) || (countIn1 != 0 && countIn2 == 0)
				|| (countOut1 == 0 && countOut2 != 0) || (countOut1 != 0 && countOut2 == 0)) {
			return false;
		}

		// Compute the minimum node in the second graph, depending on the
		// configuration of the in and out arrays, as specified in the original
		// paper
		int source, target;
		if (countOut1 != 0 && countOut2 != 0) {
			target = getMinimum(out2, core2);
		} else if (countIn1 != 0 && countOut2 != 0) {
			target = getMinimum(in2, core2);
		} else if (countIn1 == 0 && countIn2 == 0 && countOut1 == 0 && countOut2 == 0) {
			target = getMinimumEmpty();
		} else {
			return false;
		}

		if (target == -1) {
			// Set of possible pairs is empty
			return false;
		}

		source = getNextSource(-1);
		while (source != -1) {
			// Iterate over all possible vertices in the first graph
			if (isFeasible(source, target, countIn1, countOut1, countIn2, countOut2)) {
				// If the mapping (source,target) is feasible, add it and
				// continue the recursion
				addPair(t, source, target);
				boolean result = recursionStep(t + 1);

				// If the mapping is ok, return true, otherwise revert to the
				// last known configuration
				if (!result) {
					revert(t, source, target);
				} else {
					return true;
				}
			}

			source = getNextSource(source);
		}

		return false;
	}

	/**
	 * Add the pair (<i>source</i>, <i>target</i>) to the current mapping
	 * 
	 * @param t
	 *            Current recursion depth
	 * @param source
	 *            Vertex in the first graph
	 * @param target
	 *            Vertex in the second graph
	 */
	private void addPair(int t, int source, int target) {
		// Set the correspondence between the two vertices
		core1[source] = target;
		core2[target] = source;

		// Update the in and out arrays according to the new correspondence
		if (in1[source] == 0) {
			in1[source] = t;
			countIn1++;
		}
		if (out1[source] == 0) {
			out1[source] = t;
			countOut1++;
		}

		if (in2[target] == 0) {
			in2[target] = t;
			countIn2++;
		}

		if (out2[target] == 0) {
			out2[target] = t;
			countOut2++;
		}

		for (int i = 0; i < noVertices; i++) {
			if (graph1[source][i] != 0 && out1[i] == 0) {
				out1[i] = t;
				countOut1++;
			}

			if (graph1[i][source] != 0 && in1[i] == 0) {
				in1[i] = t;
				countIn1++;
			}

			if (graph2[target][i] != 0 && out2[i] == 0) {
				out2[i] = t;
				countOut2++;
			}

			if (graph2[i][target] != 0 && in2[i] == 0) {
				in2[i] = t;
				countIn2++;
			}
		}
	}

	/**
	 * Revert all arrays to the previous version, i.e. before the correspondence
	 * (<i>source</i>, <i>target</i>) has been added
	 * 
	 * @param t
	 *            Current recursion depth
	 * @param source
	 *            Vertex in the first graph
	 * @param target
	 *            Vertex in the second graph
	 */
	private void revert(int t, int source, int target) {
		// Restore the correspondences array
		core1[source] = -1;
		core2[target] = -1;

		// Restore the in/out arrays
		if (in1[source] == t) {
			in1[source] = 0;
			countIn1--;
		}
		if (out1[source] == t) {
			out1[source] = 0;
			countOut1--;
		}

		if (in2[target] == t) {
			in2[target] = 0;
			countIn2--;
		}

		if (out2[target] == t) {
			out2[target] = 0;
			countOut2--;
		}

		for (int i = 0; i < noVertices; i++) {
			if (graph1[source][i] != 0 && out1[i] == t) {
				out1[i] = 0;
				countOut1--;
			}

			if (graph1[i][source] != 0 && in1[i] == t) {
				in1[i] = 0;
				countIn1--;
			}

			if (graph2[target][i] != 0 && out2[i] == t) {
				out2[i] = 0;
				countOut2--;
			}

			if (graph2[i][target] != 0 && in2[i] == t) {
				in2[i] = 0;
				countIn2--;
			}
		}
	}

	/**
	 * Check if the mapping from <i>source</i> to <i>target</i> is feasible
	 * 
	 * @param source
	 *            Vertex in the first graph
	 * @param target
	 *            Vertex in the second graph
	 * @param countIn1
	 *            Number of elements in in1
	 * @param countOut1
	 *            Number of elements in out1
	 * @param countIn2
	 *            Number of elements in in2
	 * @param countOut2
	 *            Number of elements in out2
	 * @return True if the correspondence (<i>source</i>, <i>target</i>) is
	 *         feasible, false otherwise
	 */
	private boolean isFeasible(int source, int target, int countIn1, int countOut1, int countIn2,
			int countOut2) {
		for (int i = 0; i < noVertices; i++) {
			// Check nodes from source
			if (graph1[source][i] != 0) {
				if (core1[i] != -1 && graph2[target][core1[i]] == 0) {
					return false;
				} else if (core1[i] == -1 && out1[i] == 0) {
					countOut1++;
				}
			}

			// Check nodes to source
			if (graph1[i][source] != 0) {
				if (core1[i] != -1 && graph2[core1[i]][target] == 0) {
					return false;
				} else if (core1[i] == -1 && in1[i] == 0) {
					countIn1++;
				}
			}

			// Check nodes from target
			if (graph2[target][i] != 0) {
				if (core2[i] != -1 && graph1[source][core2[i]] == 0) {
					return false;
				} else if (core2[i] == -1 && out2[i] == 0) {
					countOut2++;
				}
			}

			// Check nodes to target
			if (graph2[i][target] != 0) {
				if (core2[i] != -1 && graph1[core2[i]][source] == 0) {
					return false;
				} else if (core2[i] == -1 && in2[i] == 0) {
					countIn2++;
				}
			}
		}

		// Check if the new number of elements in the arrays match, according to
		// the description in the original paper
		if (countOut1 != countOut2 || countIn1 != countIn2) {
			return false;
		}

		return true;
	}

	/**
	 * Get the next vertex in the first graph to be considered
	 * 
	 * @param lastIndex
	 *            Last vertex that was considered in the current iteration
	 * @return Next vertex to be considered in the current iteration
	 */
	private int getNextSource(int lastIndex) {
		if (countOut1 != 0 && countOut2 != 0) {
			return getNext(out1, core1, lastIndex);
		} else if (countIn1 != 0 && countOut2 != 0) {
			return getNext(in1, core1, lastIndex);
		} else if (countIn1 == 0 && countIn2 == 0 && countOut1 == 0 && countOut2 == 0) {
			for (int i = lastIndex + 1; i < noVertices; i++) {
				if (core1[i] == -1) {
					return i;
				}
			}
		}

		return -1;
	}

	/**
	 * Get the next vertex in the array <i>array</i> that has not been mapped
	 * yet, but belongs to an in/out array
	 * 
	 * @param array
	 *            In / out array
	 * @param core
	 *            Correspondences array
	 * @param position
	 *            Last vertex considered in the current iteration
	 * @return Next vertex in <i>array</i> that has not been mapped yet, but
	 *         belongs to an in/out array
	 */
	private int getNext(int[] array, int[] core, int position) {
		for (int i = position + 1; i < array.length; i++) {
			if (array[i] != -1 && core[i] == -1) {
				return i;
			}
		}

		return -1;
	}

	/**
	 * Get the first vertex in <i>array</i> that has not been mapped yet, but
	 * belongs to an in/out array
	 * 
	 * @param array
	 *            In/out array
	 * @param core
	 *            Correspondences array
	 * @return First vertex in <i>array</i> that has not been mapped yet, but
	 *         belongs to an in/out array
	 */
	private int getMinimum(int[] array, int[] core) {
		for (int i = 0; i < array.length; i++) {
			if (array[i] != 0 && core[i] == -1) {
				return i;
			}
		}

		return -1;
	}

	/**
	 * Get the first vertex in <i>core2</i> that has not been mapped yet
	 * 
	 * @return First vertex in the inverse mapping that has not been mapped yet
	 */
	private int getMinimumEmpty() {
		for (int i = 0; i < noVertices; i++) {
			if (core2[i] == -1) {
				return i;
			}
		}

		return -1;
	}

	@Override
	public long getTotalTime() {
		return totalTime;
	}
}
